package 力扣_简单题;

/**
 * @author 连安利
 * @version 1.0
 * @date 2021/3/30 16:10
 */
public class 最长公共前缀 {
    public static void main(String[] args) {
        String strs[] = {"abcdef","abca","abfefg"};
        System.out.println(longestCommonPrefix(strs));
    }
//    方法一：横向扫描
    public static String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for(int i = 1; i < strs.length; i++){
            int index = 0;
            if(prefix.length() == 0){
                return "";
            }
//            遍历前缀数组和第二个字符串，得到两者的公共最大前缀数组
            while(index < prefix.length()){
//                注意要先判断index不能大于等于要比较的字符串的长度，不然就数组越界
                if(index < strs[i].length() && prefix.charAt(index)== strs[i].charAt(index) ){
                    index++;
                }
                else break;
            }
            prefix = prefix.substring(0,index);
        }
        return prefix;
    }
//    方法二：纵向扫描
    public static String longestCommonPrefix2(String[] strs) {
        if(strs == null || strs.length == 0) return "";
//纵向扫描，扫描第一个字符串的每个字符
        for(int i = 0; i < strs[0].length(); i++){
//            比较整个数组元素的当前位置的字符是否相等
            for(int j = 1; j < strs.length ;j++){
//                   如果某个字符串走到尽头了或者某个字符串的字符不等于第一个字符串的当前字符，那么就返回结果
//            i == strs[j].length()  精髓！！！
                if(i == strs[j].length() || strs[j].charAt(i) != strs[0].charAt(i)){
                    return strs[0].substring(0,i);
                }
            }
        }
//        如果上面的遍历完没有返回，那么就只有可能是第一个字符串就是最大公共前缀
        return strs[0];
    }
}
